package com.lucien.Practice;

import java.util.Stack;

public class LinkedListDemo01 {
    public static void main(String[] args) {
        Student student1 = new Student(1,"女","小芳");
        Student student2 = new Student(5,"女","小花");
        Student student3 = new Student(4,"男","梨子");
        Student student4 = new Student(3,"男","小明");
        Student student5 = new Student(3,"女","阿放");

        linkedlist linkedlist = new linkedlist();
        linkedlist.addByOrder(student1);
        linkedlist.addByOrder(student2);
        linkedlist.addByOrder(student3);
        linkedlist.addByOrder(student4);
        linkedlist.addByOrder(student5);

        linkedlist.list();

        System.out.println("更新后的链表");
        Student student=new Student(1,"男","路飞");
        linkedlist.update(student);
        linkedlist.list();

        System.out.println("删除后的链表");
        linkedlist.delte(1);
        linkedlist.list();

        System.out.println(getLength(linkedlist.getHead()));
        System.out.println(getLastStudent(linkedlist.getHead(),2));

//        System.out.println("反转后的链表");
//        reverseList(linkedlist.getHead());
//        linkedlist.list();

        System.out.println("逆序打印单链表");
        reversePrint(linkedlist.getHead());
    }

    //节点个数(头节点除外)
    public static int getLength(Student head){
        int len =0;
        Student cur = head.next;
        if (head.next == null){
            return  0;
        }
        while (cur != null){
            len++;
            cur = cur.next;
        }
        return len;
    }


    //获取倒数第k个节点
    public static Student getLastStudent(Student head,int index){
        if (head.next == null){
            return null;
        }
        int size = getLength(head);
        if (index <=0 || index>size){
            return null;
        }
        Student temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //将链表反转
    public static void reverseList(Student head){
        if (head.next == null || head.next.next == null){
            return;
        }
        Student temp = head.next;
        Student next = null;
        Student resHead = new Student(0,"","");
        while (temp != null){
            next = temp.next;
            temp.next = resHead.next;
            resHead.next = temp;
            temp = next;
        }
        head.next = resHead.next;
    }

    //逆序打印单链表
    public static void reversePrint(Student head){
        if (head.next == null){
            return;
        }
        Stack<Student> stack = new Stack<Student>();
        Student cur = head.next;
        while (cur != null){
            stack.push(cur);
            cur=cur.next;
        }
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}
class linkedlist{
    private Student head = new Student(0,"","");

    public Student getHead(){
        return head;
    }
        //添加，不排序
        public void add(Student student){
            Student temp = head;
            while (true){
                if (temp.next == null){
                        break;
                }
                temp=temp.next;
            }
            temp.next = student;
        }
        //显示链表
        public void list(){
            if (head.next == null){
                System.out.println("链表为空");
                return;
            }
            Student temp = head.next;
            while (true){
                if (temp == null){
                    break;
                }
                System.out.println(temp);
                temp = temp.next;
            }
        }
        //添加 排序
        public void addByOrder(Student student){
            Student temp = head;//辅助节点
            boolean flag = false;
            while (true){
                if (temp.next == null) {//已经到链表最后
                    break;
                }
                if (temp.next.no > student.no) {//已经找到，在temp后面添加
                    break;
                }else if (temp.next.no == student.no){//加入的编号已经存在
                    flag=true;
                    break;
                }
            temp = temp.next;

            }
            if (flag){
                System.out.printf("添加编号%d 已经存在\n",student.no);
            }else{
             student.next = temp.next;
             temp.next = student;
            }
        }

        //更新
        public void update(Student newStudent){
            if (head.next ==null){
                return;
            }
            Student temp = head.next;
            boolean flag = false;
            while (true){
                if (temp.next ==null){
                    break;
                }
                if (temp.no == newStudent.no){
                    flag = true;
                    break;
                }
                temp=temp.next;
            }
            if (flag){
                temp.name = newStudent.name;
                temp.sex = newStudent.sex;
            }else{
                System.out.printf("没有找到编号为%d 的节点",newStudent.no);
            }
        }

        //删除节点
        public void delte(int no){
            Student temp = head;
            boolean flag = false;
            if (head.next == null){
                return;
            }
            while (true){
                if (temp.next == null){
                    break;
                }
                if (temp.next.no == no){
                    flag=true;
                    break;
                }
                temp=temp.next;
            }
            if (flag){
                temp.next = temp.next.next;
            }else{
                System.out.printf("待删除的节点%d不存在",no);
            }
        }
}

class Student{
    public int no;
    public String sex;
    public String name;
    public Student next;

    public Student(int no,String sex,String name){
        this.no=no;this.sex=sex;this.name=name;
    }
    @Override
    public String toString() {
        return "student{" +
                "no=" + no +
                ", sex='" + sex + '\'' +
                ", name='" + name + '\'' +
                '}';
    }
}
